package main

import "fmt"

/*
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
*/

//滑动窗口+map
func lengthOfLongestSubstring1(s string) int {
	var n = len(s)
	if n <= 1 {
		return n
	}
	var left, right, window = 0, 0, make(map[byte]bool, 26) //左右指针索引 存放目前无重复最长子字符串的滑动窗口map
	var maxLen = 1
	for right < n {
		var rightChar = s[right]
		for window[rightChar] { //循环判断右指针元素是否与目前最长子字符串中的元素重复 一直删左指针元素直到无重复元素
			delete(window, s[left]) //重复 从map中删除最左边的值
			left++                  //左指针移动
		}
		if right-left+1 > maxLen {
			maxLen = right - left + 1
		}
		window[rightChar] = true //将刚出现的新的元素 加入到map中
		right++                  //右指针移动
	}
	return maxLen
}

//列表做哈希表+双指针
func lengthOfLongestSubstring2(s string) int {
	//列表做哈希表 记录每个元素在string中的索引
	location := [255]int{}
	for i := range location {
		location[i] = -1 //将所有初始值设为-1
	}
	maxLen, left := 0, 0 //最大长度 左指针
	for right, v := range s {
		if location[v] >= left { //判断是否出现重复元素
			left = location[v] + 1 //出现重复元素 左指针移动
		} else if right-left+1 > maxLen { //判断右指针与左指针之间的元素数量是否大于之前的最大元素数量
			maxLen = right - left + 1 //是 更新maxLen
		}
		location[v] = right //修改map的里最长子字符串每个元素的索引
	}
	return maxLen
}

func main() {
	s := "abcabcda"
	fmt.Println(lengthOfLongestSubstring1(s))
}
